package com.shm.leetcode;

/**
 * 507. 完美数
 * 对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。
 *
 * 给定一个 整数 n， 如果是完美数，返回 true，否则返回 false
 *
 *
 *
 * 示例 1：
 *
 * 输入：num = 28
 * 输出：true
 * 解释：28 = 1 + 2 + 4 + 7 + 14
 * 1, 2, 4, 7, 和 14 是 28 的所有正因子。
 * 示例 2：
 *
 * 输入：num = 6
 * 输出：true
 * 示例 3：
 *
 * 输入：num = 496
 * 输出：true
 * 示例 4：
 *
 * 输入：num = 8128
 * 输出：true
 * 示例 5：
 *
 * 输入：num = 2
 * 输出：false
 *
 *
 * 提示：
 *
 * 1 <= num <= 108
 * @author SHM
 */
public class CheckPerfectNumber {
    public boolean checkPerfectNumber(int num) {
        int sum = 0;
        for (int i = 1; i < num; i++) {
            if (num%i==0){
                sum+=i;
            }
        }
        return sum==num;
    }

    /**
     * 方法一：枚举
     * 我们可以枚举 \textit{num}num 的所有真因子，累加所有真因子之和，记作 \textit{sum}sum。若 \textit{sum}=\textit{num}sum=num 则返回 \texttt{true}true，否则返回 \texttt{false}false。
     *
     * 在枚举时，我们只需要枚举不超过 \sqrt\textit{num}
     * num
     * ​
     *   的数。这是因为如果 \textit{num}num 有一个大于 \sqrt\textit{num}
     * num
     * ​
     *   的因数 dd，那么它一定有一个小于 \sqrt\textit{num}
     * num
     * ​
     *   的因数 \dfrac{\textit{num}}{d}
     * d
     * num
     * ​
     *  。
     *
     * 在枚举时，若找到了一个
     * 复杂度分析
     *
     * 时间复杂度：O(\sqrt\textit{num})O(
     * num
     * ​
     *  )。
     * 空间复杂度：O(1)O(1)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/perfect-number/solution/wan-mei-shu-by-leetcode-solution-d5pw/
     * @param num
     * @return
     */
    public boolean checkPerfectNumber_2(int num) {
        if (num==1){
            return false;
        }
        int sum = 1;
        for (int i = 2; i*i <= num; i++) {
            if (num%i==0){
                sum+=i;
                if (i*i<num){
                    sum+=num/i;
                }
            }
        }
        return sum==num;
    }
}
